home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 051-075 / disk_065 / prep / prep.doc < prev    next >
Text File  |  1992-05-06  |  30KB  |  702 lines

  1.                              PREP v. 2.1
  2.  
  3.                     Copyright (C) 1985,1986 P.R.Ove
  4.                      All rights reserved (sort of)
  5.  
  6.      Suggestions and comments regarding this program are welcome,
  7. preferably in the form of code segments.  I will make an effort to
  8. incorporate any suggestions and maintain an "official" version of
  9. this program on the net.  Those whose contributions are incorporated
  10. will be noted in this doc file.
  11.      Only the source for this program is copyrighted.  The executable
  12. files, doc files, demos, and headers are entirely in the public domain.
  13.      As to the source, I have no objection to it being incorporated as
  14. a whole or in part in other software, as long as you say nice things
  15. about me in the docs and include my copyright notice and documentation.
  16. The source is available on net.sources, or I can email it (binaries as
  17. well if you have no C compiler).  The source may be freely distributed
  18. under these conditions.
  19.      This program is primarily intended for those that are forced to
  20. use fortran but would rather not, such as Cray users (currently fortran
  21. is the only compiler that vectorizes automatically on the Cray XMP).
  22. If you know someone suffering from this disease, please provide them
  23. with this relief package.
  24.  
  25. Currently the program has been tested on:
  26.     1) MSDOS 80*86 machines
  27.     2) Intel iPSC (80286, Xenix)
  28.     3) Sun 3 (BSD Unix)
  29.     4) Definicon DSI-020
  30.     5) Cray XMP (Cray C 1.0)
  31.     6) Gould 9000 (UTX)
  32.     7) VAX (Ultrix & BSD Unix)
  33.     8) Alliant FX/8
  34. NOTE: select a machine specific #define if using the DSI-020 
  35.       SVS compiler or the Cray compiler.  This is located at the
  36.       beginning of the file prep.h.
  37.  
  38.     At the moment comments should be directed to 14004@ncsavmsa.bitnet
  39. (or equivalently 14004@ncsaa.cso.uiuc.edu), or prove@uiucmvd.bitnet,
  40. or prove@tcgould.tn.cornell.edu.
  41.  
  42. Version 2.1 fixes and additions:
  43. 1) Cleaned up some embarrassing bugs.
  44. 2) Macros can now be undefined.
  45. 3) Memory is released when a macro is redefined or deleted.
  46. 4) Macro searching is somewhat faster (especially for long macro names),
  47.    using the Boyer-Moore algorithm.  This improvement made use of some
  48.    code from "bm", a public domain (I hope) fgrep-like utility written
  49.    by Peter Bain.
  50. 5) Conditional compilation directives (#ifdef, #ifndef, #else, #endif) added.
  51. 6) ; is now used to allow comments on the same line with a statement.
  52. 7) All switches are now accepted in either case (for case insensitive
  53.    shells like VMS).
  54.  
  55. Planned improvements:
  56. 1) Escapes for special characters in macro names.
  57. 2) ANSI-F88 vector statement support.
  58.  
  59.  
  60.  
  61. Introduction
  62.  
  63.      This documentation describes the use of PREP, a preprocessor for 
  64. fortran.  As an alternative to ratfor, PREP offers a few advantages.
  65. These include better macro facilities and a concise shorthand for array
  66. and vector statements.  In addition, all of the standard flow control
  67. constructs of forth are supported.  It is probably possible to emulate
  68. some of ratfor's syntax using PREP's macro processor to modify the flow
  69. control commands.  It is written is generic c and will run on nearly any
  70. machine/compiler combination.  Perhaps the greatest advantage is that
  71. the source is freely available.
  72.      PREP does not do everything, and in particular does not offer any
  73. help with the deficiency of data structures in fortran.  It also does not
  74. understand fortran, and will quite happily produce nonsense code if so
  75. instructed.  It will detect errors in its own syntax, but errors in 
  76. fortran will be left for the compiler.  Therefore debugging will 
  77. unfortunately involve looking at the fortran output, which can be quite
  78. ugly.  These problems are shared with ratfor.
  79.      The vector statement notation makes it possible to incorporate do
  80. loop unrolling automatically to any depth, which for certain classes of
  81. loops on certain machines (memory bound loops on vector machines) will
  82. improve performance.  On the Cray XMP performance for certain loops
  83. was increased from the normal 50 Mflops to a maximum of 80 Mflops when
  84. unrolled to a depth of 16.  On machines with many parallel paths to
  85. memory (parallel processors with compilers that optimize loops over
  86. the nodes) there may also be situations where this is advantageous.
  87.      Although the syntax is similar to forth, the spirit of forth is
  88. totally absent.  The macros are really macros, not colon definitions,
  89. and recursive macro definitions will cause an error during expansion.
  90. Postfix notation would only cause confusion, being in conflict with
  91. fortran conventions, and is not used.
  92.     The macro processor can be considered a pre-preprocessor.  The
  93. order of translation is:
  94.  
  95.     1) file inclusion & conditional compilation
  96.     2) macro processing
  97.     3) flow control extensions
  98.     4) vector statements
  99.  
  100. Note that because of this the flow control syntax can be modified
  101. at the macro level.  Although this order of translation holds
  102. rigorously, PREP is a one pass processor and makes no temporary
  103. files.
  104.      Macro definitions can be imbedded in the program file or in
  105. files that can later be included.  Some common definitions mapping
  106. certain symbols ( &, <=, !=, etc ) to their fortran equivalents ( .and.,
  107. .le., .ne., etc ) are stored in the file premac.h.  These can be made
  108. active by placing the statement ' #include "premac.h" ' in the program
  109. file, or by using the -i switch from the command line.
  110.     The nesting limit for all loops is defined by an internal constant
  111. NESTING, which is set to a number like 10 or 20 (implementation 
  112. dependent).  The flow control directives are permitted inside vector
  113. loops, but since they will inhibit Cray vectorization of those loops it
  114. may be best to avoid this.  One of the reasons for using the vector
  115. shorthand is that it encourages programming in a style that can be
  116. easily vectorized by the compiler.
  117.     This program attempts to avoid all fixed limits on data structures,
  118. and instead allocates memory when needed.  The flow control directives
  119. do not adhere to this philosophy, since the maximum expansion length
  120. can be determined in advance and processing is faster without continual
  121. reallocation of memory.  Fairly robust memory management is used by the
  122. macro processor and input routines (there is no source line length limit
  123. other than any limitations imposed by the system).  Recursive macro
  124. definitions are accepted during the definition phase, but will cause an
  125. error during expansion.  When a macro is expanded more than the limit
  126. (100 or so per line, but implementation dependent) the program will abort
  127. with a recursion error message, but it is conceivable (if the memory of
  128. the machine is small and the macro definitions are very long) that a
  129. memory allocation error will occur before this.
  130.     In most cases the flow control directives must be the first word
  131. on the line (PREP is line oriented like fortran and unlike c).  The
  132. only exception is that directives and fortran code can be on the same
  133. line after an OF statement.  Any delimiters (){}[]'" may be used in the
  134. logical expressions ( i.e.  leave [ i == 1 ] ).  Macro definitions
  135. must use () for the parameter block however (to allow macro names
  136. containing the character {, for instance), and macro names cannot contain
  137. the open parens or whitespace characters.
  138.  
  139.  
  140. Running PREP
  141.  
  142.      The command line interface and program function is identical 
  143. regardless of the machine (so far).  The syntax is
  144.  
  145. prep -x -x .... <file>
  146.  
  147. where file is the first name of the file and the extension is assumed
  148. to be P.  The output file will have the extension F.  x represents
  149. a command line option:
  150.  
  151.  Switches:
  152.    -c        keep comments (truncated at column 72)
  153.    -u        keep underline characters
  154.    -m        only do macro substitution (==> -c and -u as well, and
  155.         prevents file includes (except -i switch).
  156.    -i    <file>    include <file> before processing
  157.    -r n        unroll vector loops to depth n
  158.    -l n        unroll loops with n or fewer lines
  159.    -d   <name>    define <name> as a macro, equivalent to : name 1 ;
  160.    -?        write message about allowed switches
  161.  
  162.      If no file is present standard input and output are used.  The -i
  163. switch requires the full path name of the include file.  All switches
  164. and arguments must be separated by blanks, nothing like -mcdMAC is
  165. permitted.
  166.      Normally underline characters and comment records are eliminated
  167. unless overridden with a switch.  Quoted underlines (the fortran quote
  168. character is the apostrophe) are never deleted.  In general quoted
  169. characters are safe from PREP, as is text in comment records.  Comments
  170. on the same line with source (separated with ';') will not be kept even
  171. if -c is specified.  They are only preserved by -m, in which case they
  172. will be processed for macros.  Comment records with a ';' as the first
  173. character are treated as though they were commented with 'c'.  Since
  174. ';' is also the signal to end a macro, it can't be used as a comment
  175. delimeter in macro definitions.
  176.      The -m switch is useful for converting existing programs to PREP
  177. format.  It turns off all PREP functions except macro substitution.  To
  178. partially convert a fortran program, enter:
  179.  
  180. prep -m -i fix.h <prog.f >prog.p
  181.  
  182. The file fix.h contains the inverse definitions of premac.h.  A side
  183. effect of PREP on DOS machines is that the terminating control-z is
  184. removed, which is useful if the fortran code is to be transferred to
  185. another machine.  Running the above command without the -i switch and
  186. without any internal macro definitions, it will do nothing but remove the
  187. control-z.
  188.      If the argument for -r is omitted the default is 8.  If -r is not
  189. present then unrolling will not be done at all unless turned on by an
  190. internal directive.  The command line switch will not override imbedded
  191. unrolling commands.  If -l is omitted the default is 1000, while if the
  192. argument is omitted the default is 1.
  193.      Versions for Intel 80*** based machines come compiled for small
  194. and large memory models.  The large model version is quite large
  195. itself.  It is only necessary to use the large model if the memory
  196. is needed for many very long macro definitions, which are memory resident.
  197. If you have a memory allocation error with the small version try the
  198. other.  The large one is called bigprep.exe.  Since I am now distributing
  199. the source you can do what your want.
  200.  
  201.  
  202.  
  203.  
  204. Summary of Features
  205.  
  206.     The extensions can be broken up into four classes: 1) including
  207. files & conditional compilation, 2) macro definition/expansion,
  208. 3) flow control directives, and 4) vector notation.  These will be
  209. discussed in this order, which is also the order in which they are
  210. processed.
  211.  
  212.  
  213.  
  214. Included files & conditional compilation.
  215.   example:
  216.   #include "premac.h"
  217.  
  218.      Normally fortran incudes files with the directive "include". 
  219. Incidentally, using cft and precomp on a cray files are included with
  220. "use" so if you are using a cray you may find it convenient to define
  221. "include" equivalent to "use" with
  222.     : include[x]    use x ;
  223. so that "include 'file'" will be translated to "use file".  Prep will
  224. include a file if it finds an include directive ( #include "file" )
  225. in the source, or if the -i switch is used from the command line.  Included
  226. files can be nested, probably about 10 deep.  Only the current directory is
  227. searched, and PREP will terminate if the file is not found.  To include
  228. a file in another directory the full pathname must be used.
  229.      The conditional compilation directives are similar to those of the
  230. C preprocessor, but not quite the same.  Since & and | are legitimate
  231. macro names, no expressions are permitted (this is of course a rather
  232. poor excuse, the real reason being laziness :-)  The syntax is:
  233.  
  234. #ifdef name1 name2 name3.... namen
  235. lines of code
  236. #endif
  237.  
  238. The lines of code will be processed if any of the names is currently
  239. defined as a macro.  #ifdef can be abbreviated as #if.  #ifndef is 
  240. similar, except that the the lines will be processed if any of the
  241. names is not a macro.  "Not being processed" means that the lines
  242. will be stricken from the resulting fortran program altogether.
  243. #else is also supported, but not #elif.  This simple set of 
  244. directives is probably sufficient, but expression evaluation and
  245. a (#case, #of, #default, #endcase) would be useful.
  246.  
  247. Macros
  248.      The style is similar to that of C #define macros, except
  249. that : is used instead of #define and ; terminates the macro.  No
  250. special character is needed to continue to the next line.  Non-C syntax
  251. is used to allow both PREP macros and C preprocessor macros in the
  252. same program, and because I don't wish to make any guarantees about
  253. compatibility with cpp.
  254.      Recursive definitions are permitted, but will cause an abort
  255. (and possibly a memory allocation error) on expansion.  For each
  256. line submitted to expand_macros, a count of is kept for each
  257. stored macro indicating how many times it has been expanded in
  258. the current line.  When this exceeds MAX_CALLS, the program 
  259. assumes a macro definition is recursive and stops.  Macros
  260. are expanded starting with the one with the longest name, so that
  261. if the definitions
  262.  
  263.    : >=        .ge. ;
  264.    : >        .gt. ;
  265.  
  266. are in effect, >= will be changed to .ge. rather than .gt.=.  This
  267. is only a potential problem when macro names are not fully
  268. alphanumeric, since "arg" will not be flagged if "r" is defined.
  269. The underline character is considered non-alphanumeric here, for
  270. no good reason and perhaps it should not be.
  271.  
  272.      The definition phase is invoked when a leading : is found in
  273. the record.  Text is then taken until the terminating ; is found.  Text
  274. following the ; is ignored (until the next newline).  Multi-line macros
  275. are permitted: they will be converted to at least as many lines in the
  276. fortran program.  The general form of a macro definition is:
  277.  
  278.    : name( parm1, parm2, ... )    text with parameters
  279.                 more text with parameters
  280.                  "    "    "    "    ;
  281.  
  282. with 20 as the maximum number of parameters.  There must be no space
  283. between the macro name and the open delimiter of the parameter block in
  284. a definition, and the delimiters (if present) must be ().  Macro names
  285. can not contain the open parens.  Examples of macros with more than
  286. one line are:
  287.  
  288.    : }
  289.     end do ;
  290.    : {
  291.     ;
  292.  
  293. These will allow translation of ratfor style do loops:
  294.  
  295.     do i = 1, 10 { write(*,*) ' i = ', i }
  296.  
  297. is translated into:
  298.  
  299.     do i = 1, 10
  300.     write(*,*) ' i = ', i
  301.     end do
  302.  
  303. which will be translated into fortran during the flow control processing.
  304. Note that this example relies on the fact the whitespace between the
  305. macro definition and its terminating ; is significant (newline is not
  306. considered whitespace here).  This is not the case for whitespace between
  307. the name and the definition.  Failure to have a terminating ; will define
  308. the entire program to be a macro.  This could cause a memory allocation
  309. failure, as macros are stored in memory.
  310.      While in a definition the open parens must follow the name without
  311. whitespace, in the source code this requirement (and the need to use only
  312. () as delimiters) is relaxed.  Alphanumeric macros must be not be next to
  313. an alpha or number character or they will not be recognized.
  314.      The macro definition routine puts the macro string into a more easily
  315. handled format, replacing parameters in the text with n, where n is a
  316. binary value (128 to 128+MAX_TOKENS).  The macro is placed in a structure
  317. of the form:
  318.  
  319. struct Macro {
  320.     char    *name ;
  321.     char    namelength ;
  322.     char    *text ;
  323.     int    parmcount ;
  324.     int    callcount ;
  325.     int    alpha ;
  326.     unsigned short    *skip1, *skip2 ;
  327. }
  328.  
  329. where the text string has binary symbols where the parms were.  Parmcount
  330. is used to see if a parameter block should be searched for when expanding
  331. a macro.  Callcount is used to stop expansion in case of recursive
  332. definitions.  Alpha set to 1 ==> the macro name can't be next to alpha-
  333. numeric characters.  The skip parameters point to Boyer-Moore tables
  334. (except for macros with short names (currently short :== 1 character),
  335. which don't use the BM algorithm for efficiency reasons).
  336.      Caution must be exercised to avoid accidental recursive definitions
  337. involving more than one macro:
  338.  
  339.     : h    i+x ;
  340.     : i(y)    func(y) ;
  341.     : func    h ;
  342.  
  343. This will generate the successive strings (from a = func(x)):
  344.  
  345.     a = h(x)
  346.     a = i+x(x)
  347.     a = func()+x(x)
  348.     a = h()+x(x) .... and so on.  Beware.
  349.  
  350.      Macro names will not be flagged if they are quoted (with apostrophes)
  351. in the source, or if they are in comment records.
  352.      If more parameters are found than were present in the definition, the
  353. trailers are ignored.  If fewer are found they will be inserted where
  354. expected only (the missing parameters will be taken to be null strings).
  355. Parameters are separated by commas, and are only recognized if they are
  356. balanced according to delimiters.  If : MACRO(a,b) a + b ; is defined
  357. and
  358.  
  359.     MACRO " [i,j] "
  360.  
  361. is found in the text, only one parameter will be found and it will be
  362. expanded as:
  363.  
  364.     [i,j] +
  365.  
  366. It is not possible to have unbalanced delimiters in a parameter of a 
  367. macro unless the macro only has one argument.
  368.      A macro definition will override a previous definition with
  369. the same name.  The statement:
  370.  
  371. : func(x) ;
  372.  
  373. will undefine func (remove it from the macro table).  The argument
  374. is unnecessary when undefining.
  375.  
  376.  
  377.  
  378. Flow Control Extensions
  379.      These commands are based on the flow control of forth (except for
  380. the do/end_do construct).  With the exception of the OF and DEFAULT
  381. commands, no other text is allowed on the line.  If trailing text is
  382. present it is ignored, leading text will prevent PREP from seeing the
  383. command.  This includes labels: PREP command lines may not have labels
  384. unless macros are used to define labels to expand as continue statements
  385. and newlines.  The commands end_case, end_do, and leave_do can have a
  386. space instead of the underline, but the space is significant.  Of course
  387. a macro could be defined as    : enddo end_do ;.  Unlike some other
  388. languages (forth and c) where CONTINUE applies to all types of loops,
  389. here there are three CONTINUE statements (continue, continue_do, and
  390. continue_case) which apply to the three classes of loops supported by
  391. PREP.  This avoids some confusion in certain situations with nested
  392. loops of differing types.  In general for the flow control extensions,
  393. if optional expressions are omitted they are taken to be TRUE.
  394.  
  395.  
  396.  Forth style begin/while/until/again construct:
  397.      begin ... again
  398.      begin ... while (exp1) ... again
  399.      begin ... until (exp1)
  400.      leave (optional expression) to exit current level
  401.      continue (optional expression) to got back to begin
  402.  
  403.      Here the ...'s represent lines of PREP and fortran code, not on
  404. the same line with the directives.  A working example of one of these
  405. is:
  406.      begin
  407.         line of code
  408.      while ( SOME_MACRO[i] )   ; the macro evaluates to a logical expression
  409.         line of code
  410.         line of code
  411.      again
  412.  
  413. The begin ... again construct will loop forever.  Usually it will have a
  414. leave command inside ( leave [ EOF ], where EOF is a macro ), or a
  415. return to caller.  These (as with the case construct and do/end_do) may
  416. be nested ten levels deep.  The begin is always necessary, even it the
  417. next statement is while.
  418.  
  419.  
  420.  Case construct:
  421.      case ( optional exp )
  422.      of   ( exp2 )  line of code
  423.                     line of code
  424.                     continue_case ( optional logical exp )
  425.      of   ( exp3 )  line of code
  426.      default        line of code
  427.                     line of code
  428.      end_case
  429.  
  430.      This is processed by converting to if else endif expressions.  It is
  431. somewhat clearer in general.  The expressions here must NOT be logical
  432. (.eq. is used), unless CASE is followed by no parameter in which case 
  433. the OF expressions MUST be logical expressions.  Unfortunately fortran
  434. does not allow comparisons between logical expressions using .eq., so
  435. there is no way around this dilemma without having the preprocessor
  436. understand fortran to determine variable types (which in turn would
  437. require that all fortran include directives be processed).  Of course
  438. if the value is logical there is not much sense in using the case
  439. construct instead of and ordinary if/else/endif.  An example of a 
  440. case construct is
  441.  
  442.      c = getchar()    ; function that returns a character value
  443.      case ( c )
  444.      of ( 'q' )   call exit
  445.      of ( 'd' )   call dump
  446.                   continue_case ( not_done )
  447.      default      write(*,*) 'illegal character, try again'
  448.                   continue_case
  449.      end_case
  450.  
  451. In this example the continue statements pass control back to the case, so
  452. getchar is not reevaluated.  If getchar() were put in the case expression
  453. however, it would be evaluated for each OF statement as
  454.  
  455.      if ( 'q' .eq. getchar() ) etc
  456.  
  457. which is probably not what was intended.  Therefore, continue_case is rather
  458. useless here unless the value of variable c is changed by the OF clause.
  459. The example will write indefinitely if any character other than q or d
  460. is entered.  The right way to do this is by switching the 1st 2 lines:
  461.  
  462.      case ( c )
  463.      c = getchar()    ; function that returns a character value
  464.      of ( 'q' )   call exit
  465.            ...
  466.            ...
  467.      end_case
  468.  
  469. This will evaluate the function getchar on entry and once every time
  470. continue_case is encountered.  An example which uses logical expressions is
  471.  
  472.      case
  473.      c = getchar()
  474.      of ( 'q' == c ) call exit
  475.            ...
  476.      end case
  477.  
  478. The nesting limit for case constructs is again 10.  If continue_case
  479. is too long a command name, it can always be abbreviated with a macro
  480. definition (in premac.h the definition ": ->case continue_case ;" does
  481. this).
  482.  
  483.  
  484.  
  485.  do ... end_do
  486.  
  487.      The syntax here is like that of vms fortran, except for the leave_do
  488. which jumps out of the loop if the logical expression is true, and 
  489. continue_do which jumps to the end_do and continues the loop.  An
  490. example:
  491.  
  492.      do i = 1, 10
  493.     line of code
  494.      continue do ( i == 2 )    ; goes to end_do if true
  495.     line of code
  496.     line of code
  497.      leave do ( i*j == 4 )    ; exits loop if true
  498.     line of code
  499.      end do
  500.  
  501. The leave_do and continue_do commands cannot be used in normal labeled
  502. do loops.  If the logical expressions are omitted they are assumed
  503. true.
  504.  
  505.  
  506.  
  507.  
  508. Vector Arithmetic
  509.      When writing large number crunching programs in fortran it often
  510. happens that there are a large number of arrays with the same dimensions.
  511. More than likely the loop parameters will be the same for many loops,
  512. and even a simple routine may be rather long and difficult to read
  513. because of all the excess baggage.  It is therefore helpful to have
  514. a shorthand method for writing loops that use common loop parameters.
  515.      A few examples of the shorthand supported by PREP follow.
  516.  
  517.     a(#,#) = b(#,#) + 1
  518.  
  519. This has the obvious meaning that all of the elements of array a are
  520. set equal to those of b incremented by 1.  Assuming the appropriate
  521. default loop parameters have been set, this will be expanded as
  522.  
  523.     do 10001 i001 = 1, my
  524.     do 10000 i000 = 1, mx
  525.     a(i000,i001) = b(i000,i001) + 1
  526. 10000    continue
  527. 10001    continue
  528.  
  529. The labels will be generated uniquely.  The variables i000 -> i009 are
  530. reserved for this purpose.  PREP assumes that the usual fortran 
  531. conventions hold and that variables beginning with i are integers.
  532. In fortran the first index of an array changes the most rapidly as
  533. one proceeds through the memory, so the loops are always generated
  534. with the innermost loop over the first index.  This is essential for
  535. efficiency on machines with virtual memory (VAX) or those that rely
  536. on sequential addressing for vectorization (Cyber).
  537.      More than one line can be placed in the core of a loop by using
  538. square brackets to group them together.
  539.  
  540.     c(#,#) = exp( d(#,#) ) + c(#,#)
  541. [    a(#,#) = b(#,#,1)*c(#,#) - 100
  542.     x = y
  543.     d(#,#) = e(#,#)         ]
  544.  
  545. is expanded as
  546.  
  547.     do 10001 i001 = 1, my
  548.     do 10000 i000 = 1, mx
  549.     c(i000, i001) = exp( d(i000,i001) ) + c(i000,i001)
  550. 10000    continue
  551. 10001    continue
  552.     do 10003 i001 = 1, my
  553.     do 10002 i000 = 1, mx
  554.     a(i000,i001) = b(i000,i001,1)*c(i000,i001) - 100
  555.     x = y
  556.     d(i000,i001) = e(i000,i001)
  557. 10002    continue
  558. 10003    continue
  559.  
  560. Yes the output can get very ugly, but computers don't care.  PREP will 
  561. always continue to the next line if necessary so there is no need
  562. to worry about line length.
  563.     The above loops use default loop limits, and these must be set
  564. with the do_limits command.  The general form is:
  565.  
  566. do_limits [ (mi, mf, minc), (ni, nf, ninc), .... ]
  567.  
  568. The number of triples (do i000=mi, mf, minc) determines how many
  569. indices will be looped over.  If a triple has only 2 elements they are
  570. assumed to be the initial value and final value and the increment is
  571. taken to be 1.  If a triple has just one element (parens then not needed)
  572. it is assumed to be the final value and the initial value and increment
  573. are both taken to be 1.  Therefore the above examples could have their
  574. limits set with
  575.  
  576. do_limits [ mx, my ]
  577.  
  578. Usually the do_limits statement will be tucked out of the way at the
  579. beginning of the program file or in a PREP #include file.  Again the
  580. underline can be replaced by a blank.
  581.      As a rule the number of # symbols in each array should equal the
  582. number of indices implied by the current default limits.  A common
  583. exception is
  584.  
  585.     a(#) = a(#) + b(#,#)*c(#,#)
  586.  
  587. which expands as
  588.  
  589.     do 10001 i001 = 1, my
  590.     do 10000 i000 = 1, mx
  591.     a(i000) = a(i000) + b(i000,i001)*c(i000,i001)
  592. 10000    continue
  593. 10001    continue
  594.  
  595. This does a lot of dot products in parallel on a vector machine like
  596. the Cray.  The compiler will vectorize the inner loop, but is not 
  597. smart enough to realize that the vector "a" should be kept in a vector
  598. register from one outer iteration to the next, and does an unnecessary
  599. save and fetch each time.  Because this loop is memory bound (the
  600. performance is limited by the time it takes to fetch and store the
  601. data rather than the floating point speed of the machine because
  602. there are so few operations in the loop) the performance can be 
  603. increased by unrolling the loop.  This is done automatically by PREP
  604. to any depth.  Unrolling this example to a depth of 4 gives
  605.  
  606.       do 10001 i001=1,int((1.0*(( my )-1+1))/(1*4))*1*4+1-1,1*4
  607.       do 10000 i000 = 1, ( mx), 1
  608.       a(i000) = a(i000) + b(i000,i001)*c(i000,i001)
  609.       a(i000) = a(i000) + b(i000,i001+1*1)*c(i000,i001+1*1)
  610.       a(i000) = a(i000) + b(i000,i001+1*2)*c(i000,i001+1*2)
  611.       a(i000) = a(i000) + b(i000,i001+1*3)*c(i000,i001+1*3)
  612. 10000 continue
  613. 10001 continue
  614.       do 10003 i001=int((1.0*(( my )-1+1))/(1*4))*1*4+1,( my ),1
  615.       do 10002 i000 = 1, ( mx), 1
  616.       a(i000) = a(i000) + b(i000,i001)*c(i000,i001)
  617. 10002 continue
  618. 10003 continue
  619.  
  620. The second set of loops is a clean up operation.  This technique
  621. improves performance because now the compiler will see that the
  622. same vector will be used in the next vector statement and therefore
  623. keeps it in a register.  The example above which is not unrolled runs
  624. at about 50 Mflops.  Unrolling to a depth of 16 results in a speed
  625. of 80 Mflops (when mx=my=100)
  626.      Unrolling can be controlled with the command line switches
  627. mentioned earlier and with the command
  628.  
  629. unroll ( 8 )
  630.  
  631. imbedded in the source.  The depth must be explicit of course.
  632. Using the imbedded command individual loops can be controlled
  633. independently.
  634.      Unfortunately, using the same trick on more complicated loops
  635. actually degrades performance, since the loops become too
  636. complicated for the optimizer.  For this reason there is a command
  637. line switch -l n, which inhibits unrolling unless the vector
  638. statement is on n or fewer lines.  Unrolling is always disabled
  639. if the number of indices is not greater than 1, since it would
  640. serve no purpose for 1 index loops on the vector machines for
  641. which it is intended (Unrolling a 1 index loop will inhibit
  642. vectorization).  This should perhaps be a command line option
  643. as well, since scalar machines may derive some benefit for such
  644. loops.
  645.      Loops should never be unrolled unless one is certain that
  646. the result is independent of the order over which the indices are
  647. swept.  Usually if a loop is vectorizable on the Cray and can be
  648. written in this notation, it can be unrolled.  A loop such as
  649.  
  650. [    a(#,#) = i
  651.     i = i + 1
  652. ]
  653.  
  654. is not vectorizable and if unrolled the result will not be
  655. independent of the unrolling depth.  Low precision calculations may
  656. show differences depending on the depth because of round off errors.
  657. For instance, if sum is a 32 bit real and a is an array of 32 or
  658. 64 bit reals with a(i,j)=i+mi*j where the dimensions are large,
  659. the loop
  660.  
  661.     sum = sum + a(#,#)
  662.  
  663. may differ in the least significant digits when unrolled.  This is
  664. because when not unrolling (in this example) small numbers have a
  665. chance to add up before being added to large ones.  The unrolled
  666. loops may add small numbers directly to large ones and lose them.
  667. Of course this is just a precision problem and has nothing to do
  668. with the correctness of the algorithm.  Examples could just as
  669. easily be invented where the unrolled version is more accurate.
  670.      Some performance improvements have been noted for scalar
  671. machines.  Parallel processors have not yet been tested but
  672. may allow the most improvement, since the technique will be
  673. of greater assistance if the number of parallel paths to memory
  674. is increased.  In principle each processor could access a local
  675. memory store simultaneously, and unrolling would allow an 
  676. optimizing compiler to realize more easily that fetches could
  677. be done in parallel.  PREP allows such matters to be investigated
  678. without the need for a great deal of text editing to unroll
  679. loops by hand.
  680.      The program has recently been tested on an Alliant FX/8
  681. parallel processor.  This machine has 8 vector processors and 8
  682. parallel paths to a common memory, which makes it an ideal candidate
  683. for this unrolling trick.  However, the Alliant compiler is a very
  684. advanced beast, and optimizes two levels deep (vectorizes inner
  685. loops and distributes outer loops).  This eliminates any possible
  686. gains from unrolling, and in fact performance is retarded by doing
  687. so.  In principle the Alliant scheme could be implemented at the
  688. preprocessor level.  I have no immediate plans to do it, but this
  689. preprocessor might be a good starting point for such a project.
  690.  
  691. disclaimer: The unrolling feature of this program is present only
  692. because I was curious about such matters.  It should be viewed as
  693. an experimental tool.  I doubt that there exists a machine where
  694. performance can be greatly improved simply by globally unrolling
  695. the loops.
  696.  
  697.  
  698.  
  699.      If you have used this program and have any comments or 
  700. suggestions, they can be sent via lectric-mail to the addresses
  701. mentioned above.
  702.